home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / mawk10.zip / MAWK_TES.DAT < prev    next >
Text File  |  1991-10-05  |  3KB  |  108 lines
  1.  
  2. #include  <zmalloc.h>
  3.  
  4. extern unsigned hash() ;
  5.  
  6. /* An array A is a pointer to an array of struct array,
  7.    which is two hash tables in one.  One for strings
  8.    and one for doubles.
  9.  
  10.    each array is of size A_HASH_PRIME.
  11.  
  12.    When an index is deleted via  delete A[i], the
  13.    ANODE is not removed from the hash chain.  A[i].cp
  14.    and A[i].sval are both freed and sval is set NULL.
  15.    This method of deletion simplifies for( i in A ) loops.
  16.  
  17.    On the D_ANODE list, we use real deletion and move to the
  18.    front on access.
  19.  
  20.    Separate nodes (as opposed to one type of node on two lists)
  21.    to
  22.      (1) d1 != d2, but sprintf(A_FMT,d1) == sprintf(A_FMT,d1)
  23.          so two dnodes can point at the same anode.
  24.      (2) Save a little data space(64K PC mentality).
  25.  
  26.    the cost is an extra level of indirection.
  27.  
  28.    Some care is needed so that things like
  29.      A[1] = 2 ; delete A["1"] work .
  30. */
  31.  
  32. #define  _dhash(d)    (((int)(d)&0x7fff)%A_HASH_PRIME)
  33. #define  DHASH(d)     (last_dhash=_dhash(d))
  34. static  unsigned  last_dhash ;
  35.  
  36. /*        switch =======;;;;;;hhhh */
  37.  
  38. static  ANODE *find_by_sval(A, sval, cflag)
  39.   ARRAY  A ;
  40.   STRING *sval ;
  41.   int  cflag ; /* create if on */
  42. { 
  43.    char *s = sval->str ;
  44.    unsigned h = hash(s) % A_HASH_PRIME ;
  45.    register ANODE *p = A[h].link ;
  46.    ANODE *q = 0 ; /* holds first deleted ANODE */
  47.  
  48.    while ( p )
  49.    {
  50.      if ( p->sval )
  51.      { if ( strcmp(s,p->sval->str) == 0 )  return p ; }
  52.      else /* its deleted, mark with q */
  53.      if ( ! q )  q = p ;  
  54.  
  55.      p = p->link ;
  56.    }
  57.  
  58.    /* not there */
  59.    if ( cflag )
  60.    {
  61.        if ( q )  p = q ; /* reuse the deleted node q */
  62.        else
  63.        { p = (ANODE *)zmalloc(sizeof(ANODE)) ;
  64.          p->link = A[h].link ; A[h].link = p ;
  65.        }
  66.  
  67.        p->sval = sval ;
  68.        sval->ref_cnt++ ;
  69.        p->cp = (CELL *) zmalloc(sizeof(CELL)) ;
  70.        p->cp->type = C_NOINIT ;
  71.    }
  72.    return p ;
  73. }
  74.  
  75.  
  76. /* on the D_ANODE list, when we find a node we move it
  77.    to the front of the hash chain */
  78.  
  79. static D_ANODE  *find_by_dval(A, d, cflag)
  80.   ARRAY  A ;
  81.   double d ;
  82.   int cflag ;
  83. {
  84.   unsigned h = DHASH(d) ;
  85.   register D_ANODE *p = A[h].dlink ;
  86.   D_ANODE *q = 0 ; /* trails p for move to front */
  87.   ANODE *ap ;
  88.  
  89.    while ( p )
  90.        if ( p->dval == d )
  91.        { /* found */
  92.          if ( ! p->ap->sval ) /* but it was deleted by string */
  93.          { if ( q )  q->dlink = p->dlink ;
  94.            else A[h].dlink = p->dlink ;
  95.            zfree(p, sizeof(D_ANODE)) ;
  96.            break ; 
  97.          }
  98.          /* found */
  99.          if ( !q )  return  p ; /* already at front */
  100.          else /* delete to put at front */
  101.          { q->dlink = p->dlink ; goto found ; }
  102.        }
  103.        else
  104.        { q = p ; p = p->dlink ; }
  105.  
  106. void (*signal())() ;
  107.  
  108.